% Aca va todo el codigo

% defino una mina y defino un rango de valores posibles.
% valor(-X).
valor(mina).
valor(X) :- between(0,8,X).

% Suponiendo una lista consistente, tomamos la longitud de la lista
% como la cantidad de filas y la longitud del primer elemento
% de la lista como la cantidad de la lista.
% dim(+T, -C, -F)
dim([X|L], C, F) :- length(X, C), length(L, D), F is D + 1.

% obtengo la #filas y #columnas de T e itero desde el primer valor 
% hasta la #fil y #col
% pos(+T, -C, -F)
pos(T, C, F) :- dim(T, X, Y), between(1, Y, F), between(1, X, C).

% por construccion. Si el primer elemento de L es nonvar,
% entonces tiene que estar en R. Sino, sigo hasta que sea vacia
% nonvars(?L, -R)
nonvars([],[]).
nonvars([X|L], [X|R]) :- nonvar(X), nonvars(L,R),!.
nonvars([X|L], R) :- var(X), nonvars(L,R).

% filtro los elementos instanciados y chequeo cuantos son minas.
% cant_minas(?L, -N)
cant_minas(L, N) :- nonvars(L, R), cant_minas_aux(R, N).
cant_minas_aux([], 0).
cant_minas_aux([mina|L], N) :- cant_minas_aux(L, M), N is M + 1, !.
cant_minas_aux([X|L], N) :- X \= mina, cant_minas_aux(L, N), !.

% ejercicio 6

% enesimo(-X,+N,+L) 
enesimo(X,1,[X|_]) :- !.
enesimo(X,N,[_|L]):- R is N-1, enesimo(X,R,L). 

%coordenada(+T,+C,+F,-X)
coordenada(T,C,F,[]) :- not(pos(T,C,F)),!.
coordenada(T,C,F,[X]) :- pos(T,C,F), enesimo(Fila,F,T), enesimo(X,C,Fila).


% vecinos(+T,+C,+F,-L) tomo la fila F-1, F, F+1 si las hay
% y me quedo con C-1, C, C+1 menos F,C

vecinos(T,C,F,L) :- Fme1 is F-1,Cme1 is C-1,Fma1 is F+1,Cma1 is C+1,
		    coordenada(T,Cma1,Fma1,L1), append(L1,[],R1),
		    coordenada(T,C,Fma1,L2), 	append(L2,R1,R2),
		    coordenada(T,Cme1,Fma1,L3), append(L3,R2,R3),
		    coordenada(T,Cma1,F,L4), 	append(L4,R3,R4),
		    coordenada(T,Cme1,F,L5), 	append(L5,R4,R5),
		    coordenada(T,Cma1,Fme1,L6), append(L6,R5,R6),
		    coordenada(T,C,Fme1,L7), 	append(L7,R6,R7),
		    coordenada(T,Cme1,Fme1,L8), append(L8,R7,L).

%consistente(+T, +C, +F)
consistente(T, C, F) :- pos(T, C, F), coordenada(T, C, F, [mina]). 
consistente(T, C, F) :- pos(T, C, F), not(coordenada(T, C, F, [mina])), 
	vecinos(T,C,F,L), cant_minas(L, N), coordenada(T, C, F, [N]).


%consistente(+T)
consistente(T) :- setof([X,Y], pos(T, X, Y), L), 
    posiciones_consistentes(T, L).

posiciones_consistentes(_, []).
posiciones_consistentes(T, [[X,Y]|L]) :- 
    consistente(T, X, Y), posiciones_consistentes(T, L), !.

%completarA(?T)
completarA(T) :- instanciar(T), consistente(T).

instanciar(T) :- setof([X,Y], pos(T, X, Y), L), 
    posiciones_instanciadas(T,L).

posiciones_instanciadas(_,[]).
posiciones_instanciadas(T,[[C,F]|L]) :- coordenada(T,C,F,[X]),
    valor(X), posiciones_instanciadas(T,L).

%completarB(?T)
completarB(T) :- bagof([C,F], pos(T, C, F), L), 
    posiciones_consistentes_instanciadas(T,L).

% posiciones_consistentes_instanciadas(?T,-L)
% pregunto en cuanto tengo lo anterior instanciado, 
% por la forma que recorro, moviendome por las filas
% en orden creciente, cuando tengo el valor de C,F 
% puedo preguntar por C-1,F-1. Menos en la primera fila y columna. 
% Que compenso en las ultimas preguntando por el elemento anterior por 
% fila o columna, segun corresponda.

posiciones_consistentes_instanciadas(_,[]).
posiciones_consistentes_instanciadas(T,[[1,F]|L]) :- 
    coordenada(T,1,F,[X]), valor(X), 
    posiciones_consistentes_instanciadas(T,L).
posiciones_consistentes_instanciadas(T,[[C,1]|L]) :- 
    C > 1, coordenada(T,C,1,[X]), valor(X),
    posiciones_consistentes_instanciadas(T,L).
posiciones_consistentes_instanciadas(T,[[C,F]|_]) :- 
    Cm1 is C-1, Fm1 is F-1, dim(T,C,F), coordenada(T,C,F,[X]), valor(X),
    consistente(T,C,F), consistente(T,Cm1,Fm1), consistente(T,Cm1,F),
    consistente(T,C,Fm1).
posiciones_consistentes_instanciadas(T,[[C,F]|L]) :- 
    not(dim(T,C,_)), dim(T,_,F), Cm1 is C-1, Fm1 is F-1,
    coordenada(T,C,F,[X]), valor(X) , consistente(T,Cm1,F),
    consistente(T,Cm1,Fm1), posiciones_consistentes_instanciadas(T,L).
posiciones_consistentes_instanciadas(T,[[C,F]|L]) :- 
    not(dim(T,_,F)),dim(T,C,_), Cm1 is C-1, Fm1 is F-1,
    coordenada(T,C,F,[X]), valor(X) , consistente(T,C,Fm1),
    consistente(T,Cm1,Fm1), posiciones_consistentes_instanciadas(T,L).
posiciones_consistentes_instanciadas(T,[[C,F]|L]) :- 
    not(dim(T,C,_)), not(dim(T,_,F)), Cm1 is C-1, Fm1 is F-1,
    coordenada(T,C,F,[X]), valor(X) , consistente(T,Cm1,Fm1),
    posiciones_consistentes_instanciadas(T,L).

% completarC(?T)
completarC(T) :- bagof([C,F], pos(T, C, F), L), 
    posiciones_de_valores_validos_y_consistentes_instanciadas(T,L).

% posiciones_de_valores_validos_y_consistentes_instanciadas(?T,+L)
% Filtro los valores invalidos segun los vecinos ya instanciados
% de acuerdo a los criterios del enunciado. Recorro el tablero
% de la misma forma que en completarB

posiciones_de_valores_validos_y_consistentes_instanciadas(_,[]).
posiciones_de_valores_validos_y_consistentes_instanciadas(T,[[1,F]|L]) :- 
    coordenada(T,1,F,[X]), valor(X), descartar_valores(T,1,F,X), 
    posiciones_de_valores_validos_y_consistentes_instanciadas(T,L).
posiciones_de_valores_validos_y_consistentes_instanciadas(T,[[C,1]|L]) :- 
    C > 1, coordenada(T,C,1,[X]), valor(X), descartar_valores(T,C,1,X), 
    posiciones_de_valores_validos_y_consistentes_instanciadas(T,L).
posiciones_de_valores_validos_y_consistentes_instanciadas(T,[[C,F]|_]) :- 
    Cm1 is C-1, Fm1 is F-1, dim(T,C,F), coordenada(T,C,F,[X]), valor(X) ,
    descartar_valores(T,C,F,X), consistente(T,C,F), consistente(T,Cm1,Fm1),
    consistente(T,Cm1,F), consistente(T,C,Fm1).
posiciones_de_valores_validos_y_consistentes_instanciadas(T,[[C,F]|L]) :-
    not(dim(T,C,_)), dim(T,_,F), Cm1 is C-1, Fm1 is F-1, 
    coordenada(T,C,F,[X]), valor(X), descartar_valores(T,C,F,X),
    consistente(T,Cm1,F), consistente(T,Cm1,Fm1),
    posiciones_de_valores_validos_y_consistentes_instanciadas(T,L).
posiciones_de_valores_validos_y_consistentes_instanciadas(T,[[C,F]|L]) :- 
    not(dim(T,_,F)),dim(T,C,_), Cm1 is C-1, Fm1 is F-1,
    coordenada(T,C,F,[X]), valor(X), descartar_valores(T,C,F,X),
    consistente(T,C,Fm1), consistente(T,Cm1,Fm1),
    posiciones_de_valores_validos_y_consistentes_instanciadas(T,L).
posiciones_de_valores_validos_y_consistentes_instanciadas(T,[[C,F]|L]) :- 
    not(dim(T,C,_)), not(dim(T,_,F)), Cm1 is C-1, Fm1 is F-1,
    coordenada(T,C,F,[X]), valor(X), descartar_valores(T,C,F,X),
    consistente(T,Cm1,Fm1), 
    posiciones_de_valores_validos_y_consistentes_instanciadas(T,L).

% descartar_valores(+T,+C,+F,+X)
descartar_valores(T,C,F,mina) :- vecinos(T,C,F,L), nonvars(L,R),
    not(member(0,R)).
descartar_valores(T,C,F,X) :- X \= mina, vecinos(T,C,F,L), 
    cant_minas(L,N), X >= N.

% Fin codigo nuestro


pre_r(N,T) :- get_time(T1), stamp_date_time(T1, X1, 'UTC'),
    write(X1), nl, problem(N,T).
post_r(T) :- mostrar(T), get_time(T2), stamp_date_time(T2, X2, 'UTC'),
    write(X2), nl.

rA(N,T) :- pre_r(N,T), completarA(T), post_r(T).
rB(N,T) :- pre_r(N,T), completarB(T), post_r(T).
rC(N,T) :- pre_r(N,T), completarC(T), post_r(T).
	
mostrar([]).
mostrar([Fila|T]) :-
	mostrar_lista(Fila),
	mostrar(T).

mostrar_lista([]) :- nl.
mostrar_lista([H|T]) :- mostrar_celda(H), mostrar_lista(T).

mostrar_celda(C) :- nonvar(C), C == mina, write('*').
mostrar_celda(C) :-	nonvar(C), C \= mina, write(C).
mostrar_celda(C) :- var(C), write('_').


problem(t1, [[_,_],
			 [_,1]]).

problem(t2, [[_,_],
			 [_,2]]).

problem(t3, [[_,_],
			 [_,3]]).

problem(t4, [[0,_,_],
			 [_,1,_],
			 [_,_,0]]).
% Problem from Gecode/examples/minesweeper.cc  problem 0
% 
% Solution:
%  1 0 0 0 0 1
%  0 1 0 1 1 0
%  0 0 0 0 1 0
%  0 0 0 0 1 0
%  0 1 1 1 0 0
%  1 0 0 0 1 1
%
problem(0,[[_,_,2,_,3,_],
           [2,_,_,_,_,_],
           [_,_,2,4,_,3],
           [1,_,3,4,_,_],
           [_,_,_,_,_,3],
           [_,3,_,3,_,_]]).



% Problem from Gecode/examples/minesweeper.cc  problem 1
problem(1,[[_,2,_,2,1,1,_,_],
           [_,_,4,_,2,_,_,2],
           [2,_,_,2,_,_,3,_],
           [2,_,2,2,_,3,_,3],
           [_,_,1,_,_,_,4,_],
           [1,_,_,_,2,_,_,3],
           [_,2,_,2,2,_,3,_],
           [1,_,1,_,_,1,_,1]]).



% Problem from Gecode/examples/minesweeper.cc  problem 2
problem(2,[[1,_,_,2,_,2,_,2,_,_],
           [_,3,2,_,_,_,4,_,_,1],
           [_,_,_,1,3,_,_,_,4,_],
           [3,_,1,_,_,_,3,_,_,_],
           [_,2,1,_,1,_,_,3,_,2],
           [_,3,_,2,_,_,2,_,1,_],
           [2,_,_,3,2,_,_,2,_,_],
           [_,3,_,_,_,3,2,_,_,3],
           [_,_,3,_,3,3,_,_,_,_],
           [_,2,_,2,_,_,_,2,2,_]]).


% Problem from Gecode/examples/minesweeper.cc  problem 3
problem(3,[[2,_,_,_,3,_,1,_],
           [_,5,_,4,_,_,_,1],
           [_,_,5,_,_,4,_,_],
           [2,_,_,_,4,_,5,_],
           [_,2,_,4,_,_,_,2],
           [_,_,5,_,_,4,_,_],
           [2,_,_,_,5,_,4,_],
           [_,3,_,3,_,_,_,2]]).


% Problem from Gecode/examples/minesweeper.cc  problem 4
problem(4,[[0,_,0,_,1,_,_,1,1,_],
           [1,_,2,_,2,_,2,2,_,_],
           [_,_,_,_,_,_,2,_,_,2],
           [_,2,3,_,1,1,_,_,_,_],
           [0,_,_,_,_,_,_,2,_,1],
           [_,_,_,2,2,_,1,_,_,_],
           [_,_,_,_,_,3,_,3,2,_],
           [_,5,_,2,_,_,_,3,_,1],
           [_,3,_,1,_,_,3,_,_,_],
           [_,2,_,_,_,1,2,_,_,0]]).


% Problem from Gecode/examples/minesweeper.cc  problem 5
problem(5,[[_,2,1,_,2,_,2,_,_,_],
           [_,4,_,_,3,_,_,_,5,3],
           [_,_,_,4,_,4,4,_,_,3],
           [4,_,4,_,_,5,_,6,_,_],
           [_,_,4,5,_,_,_,_,5,4],
           [3,4,_,_,_,_,5,5,_,_],
           [_,_,4,_,4,_,_,5,_,5],
           [2,_,_,3,3,_,6,_,_,_],
           [3,6,_,_,_,3,_,_,4,_],
           [_,_,_,4,_,2,_,2,1,_]]).



% Problem from Gecode/examples/minesweeper.cc  problem 6
problem(6,[[_,3,2,_,_,1,_,_],
           [_,_,_,_,1,_,_,3],
           [3,_,_,2,_,_,_,4],
           [_,5,_,_,_,5,_,_],
           [_,_,6,_,_,_,5,_],
           [3,_,_,_,5,_,_,4],
           [2,_,_,5,_,_,_,_],
           [_,_,2,_,_,3,4,_]]).


% Problem from Gecode/examples/minesweeper.cc  problem 7
problem(7,[[_,1,_,_,_,_,_,3,_],
           [_,_,_,3,4,3,_,_,_],
           [2,4,4,_,_,_,4,4,3],
           [_,_,_,4,_,4,_,_,_],
           [_,4,_,4,_,3,_,6,_],
           [_,_,_,4,_,3,_,_,_],
           [1,2,3,_,_,_,1,3,3],
           [_,_,_,3,2,2,_,_,_],
           [_,2,_,_,_,_,_,3,_]]).



% Problem from Gecode/examples/minesweeper.cc  problem 8
problem(8,[[_,_,_,_,_,_,_],
           [_,2,3,4,3,5,_],
           [_,1,_,_,_,3,_],
           [_,_,_,5,_,_,_],
           [_,1,_,_,_,3,_],
           [_,1,2,2,3,4,_],
           [_,_,_,_,_,_,_]]).


% Problem from Gecode/examples/minesweeper.cc  problem 9
problem(9,[[2,_,_,_,2,_,_,_,2],
           [_,4,_,4,_,3,_,4,_],
           [_,_,4,_,_,_,1,_,_],
           [_,4,_,3,_,3,_,4,_],
           [2,_,_,_,_,_,_,_,2],
           [_,5,_,4,_,5,_,4,_],
           [_,_,3,_,_,_,3,_,_],
           [_,4,_,3,_,5,_,6,_],
           [2,_,_,_,1,_,_,_,2]]).



% From "Some Minesweeper Configurations",page 2
problem(10,[[_,_,_,_,_,_],
            [_,2,2,2,2,_],
            [_,2,0,0,2,_],
            [_,2,0,0,2,_],
            [_,2,2,2,2,_],
            [_,_,_,_,_,_]]).



% From "Some Minesweeper Configurations",page 3
% 4 solutions
problem(11,[[2,3,_,2,2,_,2,1],
            [_,_,4,_,_,4,_,2],
            [_,_,_,_,_,_,4,_],
            [_,5,_,6,_,_,_,2],
            [2,_,_,_,5,5,_,2],
            [1,3,4,_,_,_,4,_],
            [0,1,_,4,_,_,_,3],
            [0,1,2,_,2,3,_,2]]).


% Richard Kaye: How Complicated is Minesweeper?
% http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ASE2003.pdf
% 
% A Wire,page 33
% 2 solutions
%
problem(12,[[_,0,0,0,0,0,0,0,0,0,0,0,0,_],
            [_,1,1,1,1,1,1,1,1,1,1,1,1,_],
            [_,_,1,_,_,1,_,_,1,_,_,1,_,_],
            [_,1,1,1,1,1,1,1,1,1,1,1,1,_],
            [_,0,0,0,0,0,0,0,0,0,0,0,0,_]]).


% Richard Kaye: How Complicated is Minesweeper?
% http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ASE2003.pdf
% A splitter,page 35
% Many solutions...
%
problem(13,[[_,_,_,0,_,_,_,0,_,_,_],
            [_,_,_,0,1,_,1,0,_,_,_],
            [_,_,_,0,1,_,1,0,_,_,_],
            [0,0,0,0,1,1,1,0,0,0,0],
            [_,1,1,1,1,_,1,1,1,1,_],
            [_,_,_,1,_,2,_,1,_,_,_],
            [_,1,1,1,1,_,1,1,1,1,_],
            [0,0,0,0,1,1,1,0,0,0,0],
            [_,_,_,0,1,_,1,0,_,_,_],
            [_,_,_,0,1,_,1,0,_,_,_],
            [_,_,_,0,_,_,_,0,_,_,_]]).
        


% Oleg German,Evgeny Lakshtanov: "Minesweeper" without a computer
% http://arxiv.org/abs/0806.3480,page 4
problem(14,[[_,1,_,1,_,1],
            [2,_,2,_,1,_],
            [_,3,_,2,_,1],
            [1,_,3,_,2,_],
            [_,1,_,2,_,1]]).
